/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool dfs1(TreeNode* root, long long left, long long right)
    {
        if(root == nullptr) return true;

        // 如果当前节点不在区间当中，那么就不是二叉搜索树
        // if(root->val <= left || root->val >= right)
        //     return false;

        // 接下来递归左右子树，并把区间传给他们，这个区间是要依赖于它们的父节点的
        // 如果是左子树，第一轮递归就是(-∞, 根节点的值)
        // 如果是右子树，第一轮递归就是(根节点的值, +∞)
        // 这也是前序遍历的思想
        return left < root->val && root->val < right && dfs1(root->left, left, root->val) && dfs1(root->right, root->val, right);
    }

    // int pre = INT_MIN;          由于力扣的测试用例有-2147483648和2147483648(-2^31 <= Node.val <= 2^31 - 1)，所以得用long类型的正负无穷，和上面的前序遍历一样
    long long pre = LONG_MIN;
    bool dfs2(TreeNode* root)
    {
        // 这一种做法是中序遍历的思想，因为二叉搜索树的中序遍历就是一个升序数组
        // 每次遍历该节点时和上一个节点进行比较，如果比上一个节点小或者相等，那么就不是二叉搜索树
        // 由于第一个数没有上一个节点，所以上一个节点我们初始化为-∞
        // 然后递归，每次判断完更新上一个节点
        if(root == nullptr) return true;

        if(!dfs2(root->left)) return false;
        if(root->val <= pre) return false;
        pre = root->val;
        return dfs2(root->right);
    }

    bool isValidBST(TreeNode* root) {
        // 本题根据判断每个节点的值是否在合法区间来确定是否为二叉搜索树
        // 那这个合法区间怎么得来呢
        // 先初始化根节点，因为根节点不受约束，所以直接是(+∞, -∞)
        // return dfs1(root, LONG_MIN, LONG_MAX);
        return dfs2(root);
    }
};